Computer graphics, such as in computer generated images, animations and effects for motion pictures, television, computer multi-media, computer games, print and other media, often employ detailed geometric models for rendering images of three-dimensional objects. These models are typically created using commercially available computer-aided modeling and 3D scanning systems. Although some geometric models may be initially defined using high level primitives, for efficient rendering they are typically converted to their lowest common denominator form, polygonal approximations called meshes.
In the simplest case, a mesh consists of a set of vertices and a set of faces. Each vertex specifies the (x, y, z) coordinates of a point in space, and each face defines a polygon by connecting together an ordered subset of the vertices. These conjoined polygons approximate the surface geometry of the modeled object. The polygons may in general have arbitrary numbers of vertices (and even holes). For convenience, the special case of a mesh (called a "triangle mesh") in which all faces have exactly three vertices is commonly used. Arbitrary meshes composed of polygons having faces with any number of vertices equal to or greater than three can be easily converted to triangle meshes through known triangulation processes.
Complex (i.e., highly detailed) triangle meshes are notoriously difficult to render, store, and transmit. One approach to speed up rendering is to replace a complex mesh by a set of level-of-detail (LOD) approximations. A detailed mesh is used when the object is close to the viewer, and coarser approximations are substituted as the object recedes from the viewer in the image. These LOD approximations can be precomputed automatically using known mesh simplification methods. Additionally, compression schemes have been developed for efficient storage and transmission of meshes.
In my earlier U.S. patent application Ser. No. 08/586,953 entitled, "Encoding and Progressive Transmission of Progressive Meshes," filed Jan. 11, 1996 (the disclosure of which is incorporated herein by reference; hereafter referred to as the "Progressive Meshes Patent Application"), I (the inventor) disclosed the progressive mesh (PM) representation which provides a unified solution to the problems of efficiently storing, transmitting and rendering a mesh of arbitrary complexity. In short, the PM representation of an arbitrary mesh M is stored as a coarse or base mesh M.sup.0 together with a sequence of n refinement records that indicate how to incrementally refine M.sup.0 back up to the arbitrary mesh M. Each refinement record encodes information associated with a vertex split transformation that transforms the mesh by splitting a vertex v.sub.s (that is positioned between side vertices v.sub.l and v.sub.r) to add one vertex v.sub.t and up to two faces (f.sub.l ={v.sub.s, v.sub.t, v.sub.l } and f.sub.r ={v.sub.s, v.sub.t, v.sub.r }) to the mesh. The PM representation thus defines a continuous sequence of LOD approximations to the arbitrary mesh that are produced by applying the vertex split transformation defined by successive refinement records successively to the base mesh M.sup.0, resulting in a sequence of progressively more detailed meshes M.sup.0 . . . M.sup.n, M.sup.n =M. The PM representation also supports smooth visual transitions, called geomorphs, between any two of these approximations, as well as allowing progressive transmission and efficient compression of the sequence of LOD approximations of the arbitrary mesh.
For realistic rendering of an object, meshes in computer graphics (including the continuous sequence of LOD meshes defined by the PM representation) often have numerous other appearance attributes in addition to its geometric properties (i.e., vertex positions and connectivity of vertices and polygons). These additional appearance attributes can be classified into two types, discrete attributes and scalar attributes.
The discrete attributes are usually associated with faces of the mesh. A common discrete attribute, the material identifier, determines the shader function used in rendering each face of the mesh. For instance, a trivial shader function may involve a straight-forward look-up in a specified texture bitmap.
Many scalar attributes usually also are associated with a mesh. In general, the scalar attributes specify local parameters of the shader functions defined on the mesh faces. Typical examples include texture coordinates and normals which in simple cases are associated with vertices of the mesh. In the case of a simple shader function that projects a bitmap on a face of the mesh for example (e.g., the texture bitmap specified by the discrete attribute associated with the face), texture coordinates that are represented as value pairs (u,v) and associated with the vertices of the face indicate locations in the text bitmap that project onto the respective vertices. Normals which indicate a direction perpendicular to the face at the vertex, such as with a value set (n.sub.x, n.sub.y, n.sub.z) may be used for more complex shading and/or lighting effects.
There are problems, however, with storing the scalar attributes in association with vertices. In particular, it is desirable to be able to represent discontinuities in the scalar field, such as where adjacent faces of the mesh have different shading functions. For example, a mesh that models a terrain may use different texture bitmaps for areas of grass, dirt, and water. Faces of the mesh that adjoin a boundary between these areas thus would typically require different texture coordinates for indexing the different texture bitmaps at their shared vertices lying on the boundary.
One solution to the problem of representing scalar field discontinuities is to associate scalar attributes with corners of the mesh, and not simply vertices. A corner is a point on a face of the mesh at one of the face's vertices, and can be defined as a (vertex, face) value set or tuple. Scalar attributes at a corner (v, f) specify the shading parameters for face f at vertex v. For example, along a crease in the mesh (a curve on the surface across which the normal field is not continuous), each vertex has two distinct normals, one associated with the corners on each side of the crease. This is the approach taken in the PM representation disclosed in above-referenced patent application.
A drawback to this approach is that explicitly storing scalar attributes associated with each corner of the mesh consumes significant amounts of data storage capacity. Typically, a mesh with n vertices will have approximately 2n faces, and consequently approximately 6n corners. However, in general, many corners that are adjacent to a same vertex share the same scalar attributes. Thus, many of the scalar attributes associated with the corners are duplicates.
Another approach that both allows scalar field discontinuities to be represented and reduces scalar attribute storage is to store scalar attributes in association with vertices, but replicate vertices along discontinuity curves so that different scalar attributes can be stored with separate vertices at a same spatial position. This effectively separates the mesh along the discontinuity curves because faces that would otherwise adjoin from opposite sides of the curve no longer connect at a same pair of vertices. The faces instead connect to separate replicated vertices that share a common position.
Although satisfactory for static meshes, the vertex replication approach has drawbacks when applied to the PM representation and like meshes that undergo dynamic or run-time transformations. When localized modifications are made to the mesh structure (such as when a vertex split transformation is applied to one of replicated vertices at a same position), the replicated vertices can be pulled apart. This effectively introduces gaps or cracks in the mesh surface. For this reason, the vertex replication approach generally is antithetical to runtime LOD variation and progressive transmission.
The present invention provides a mesh representation for more efficient storage of scalar attributes while avoiding the tearing problem of the vertex replication approach. In accordance with one aspect of the invention, scalar attributes are stored in the mesh representation in association with wedges. A wedge is a set of contiguous, vertex-adjacent corners whose attributes are identical. This approach stores scalar attributes more efficiently than per corner storage since duplicative storage of identical scalar attributes associated with adjacent corners is avoided.
In accordance with a further aspect of the invention, the mesh representation contains a collection of vertices, a collection of wedges, and a collection of faces, where each face contains references to wedges and each wedge contains a reference to a vertex. In other words, the structure of the mesh representation is singly linked in the direction of faces to wedges to vertices. Each face also contains discrete attributes associated with the face, such as a material identifier that indicates a material color or texture mapping parameters. Each wedge contains scalar attributes associated with the wedge, such as surface normals and texture coordinates.
According to another aspect of the invention, a progressive mesh representation (herein referred to as the "efficient PM representation") contains a base mesh having the above described singly linked structure and vertex split records that identify the vertices in the vertex split transformation (i.e., the vertices denoted as (v.sub.s, v.sub.l, v.sub.r) in the above incorporated Progressive Meshes Patent Application) relative to a face of the mesh. Identifying the vertices relative to a face facilitates application of the transformation to the mesh structure that can only be traversed in the direction of faces to wedges to vertices. In the illustrated efficient PM representation for example, the split vertex (v.sub.s) is identified by an index of the vertex in an ordered list of vertices of the specified face. A first side vertex (v.sub.l) of the transformation is identified as a next of the specified face's vertices in a clockwise direction. The other side vertex (v.sub.r) of the transformation is identified by a number of clockwise face rotations about the split vertex from the first side vertex.
According to an additional aspect of the invention, wedges introduced by a vertex split transformation are encoded in a vertex split record as a set of Boolean flags (referred to herein as "corner continuities") that indicate whether each corner of the two faces introduced by the transformation have scalar attributes that are identical to or differ from its adjoining corners.
According to yet another aspect of the invention, a face of the mesh is specified in a vertex split record of the efficient PM representation as a difference from a face of an immediately preceding vertex split record. Further, the vertex split records are reordered in the efficient PM representation so as to minimize the difference of a vertex split record's face from that of the preceding vertex split record.
According to yet an additional aspect of the invention, the vertex split records of the efficient PM representation encode corner continuities, a geometry or position of the split vertex, and discrete attributes of the new faces in the vertex split transformation (e.g., material identifier) using predictive encoding. Further, a single arithmetic encoding table is used to represent the predictions of the corner continuities, split vertex geometry and new faces' discrete attributes. In general, the predictions of these values are highly correlated such that the encoding with the single arithmetic encoding table results in efficient storage of the vertex split records.
Additional features and advantages of the invention will be made apparent from the following detailed description of an illustrated embodiment which proceeds with reference to the accompanying drawings.